﻿//3296. 移山所需的最少秒数
//给你一个整数 mountainHeight 表示山的高度。
//同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
//工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
//山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
//山的高度降低 1，需要 workerTimes[i] 秒。
//山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
//返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。



class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes)
    {
        std::priority_queue<std::tuple<long long, long long, int>, vector<tuple<long long, long long, int>>, greater<>> pq;
        for (int t : workerTimes)
        {
            pq.push({ t,t,t });
        }
        long long ans = 0;
        while (mountainHeight--)
        {
            // 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
            auto [nxt, delta, base] = pq.top(); pq.pop();
            ans = nxt; // 最后一个出堆的 nxt 即为答案
            pq.emplace(nxt + delta + base, delta + base, base);
        }
        return ans;
    }
};